package com.sise.Tree;

import java.util.*;

/**
 *      144. 二叉树的前序遍历
 */
public class _144_preorderTraversal {

    // 第一种情况，通过向左节点不断遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        /**
         *  这里采用的是将所有左节点压入栈中，当取到末尾节点后，
         *  往回迭代每次获取栈顶节点，判断其是否有右节点，如果有右节点，那么对其右节点也进行此操作。
         *
         *  这里不用担心回退的时候，又将节点添加一遍。因为是 将节点添加到栈中，再将栈中节点取出来，所以不用担心同一节点添加多次的情况
         */
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                result.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.poll();
            node = node.right;      // 这里的右节点可能为 null，那么进入下一次迭代时，并不会进入 while (node != null)，而是直接进入栈顶取元素
        }
        return result;
    }

    // 第二种情况，每次将当前节点的右、左节点添加到栈中，这里的方式是将左右子棵树作为一个整体
    public List<Integer> preorderTraversal_2(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.poll();
            result.add(node.val);
            if (node.right != null) {        // 由于栈特性，故此这里先将右节点放入栈中；在下次 while 循环中，栈顶元素为左节点
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return result;
    }
}
